﻿#include "stack.h"
#include <exception>
#include <qdebug.h>

using namespace std;

template <typename T>
void MyQueue<T>::appendTail(const T &elem)
{
    m_stackIn.push(elem);
}

template <typename T>
T MyQueue<T>::deleteHead()
{
    if(m_stackIn.empty() && m_stackOut.empty())
        //        throw new exception("queue is empty.");
        throw "queue is empty.";

    if(m_stackOut.empty()){
        while(!m_stackIn.empty()){
            m_stackOut.push(m_stackIn.top());
            m_stackIn.pop();
        }
    }

    T elem=m_stackOut.top();
    m_stackOut.pop();
    return elem;
}

void Q1_test()
{
    try{
        MyQueue<int> myQueue;
        myQueue.appendTail(99);
        myQueue.appendTail(100);
        myQueue.appendTail(101);

        qDebug()<<myQueue.deleteHead();
        qDebug()<<myQueue.deleteHead();
        qDebug()<<myQueue.deleteHead();

        myQueue.appendTail(102);
        qDebug()<<myQueue.deleteHead();
    }
    catch(const char *msg){
        qDebug()<<QString(msg);
    }
}

void Q2_test()
{
    Q2_Stack stack;
    stack.push(12);
    stack.push(11);
    stack.push(8);

    qDebug()<<"Top:"<<stack.top();
    stack.pop();
    qDebug()<<"Min："<<stack.min();
}

void Q3_test()
{
    //    int inArray[]{1,2,3,4,5};
    //    int outArray[]{4,5,3,2,1};
    vector<int>pushV,popV;

    for(int i=0;i<5;++i){
        pushV.push_back(i);
        popV.push_back(5-i-1);
    }

    printf("pushV:");
    for(auto &i:pushV)
        printf("%d ",i);
    printf("\n");

    printf("popV:");
    for(auto &i:popV)
        printf("%d ",i);
    printf("\n");

    if(Q3_IsPopOrder(pushV,popV))
        qDebug()<<"测试1通过";
    else
        qDebug()<<"测试1不通过";
    //------------------------------------------------
    pushV.clear();
    popV.clear();

    printf("pushV:");
    for(auto &i:pushV)
        printf("%d ",i);
    printf("\n");

    printf("popV:");
    for(auto &i:popV)
        printf("%d ",i);
    printf("\n");
    if(Q3_IsPopOrder(pushV,popV))
        qDebug()<<"测试2通过";
    else
        qDebug()<<"测试2不通过";
    //------------------------------------------------
    pushV.clear();
    popV.clear();
    pushV.push_back(1);
    popV.push_back(1);
    printf("pushV:");
    for(auto &i:pushV)
        printf("%d ",i);
    printf("\n");

    printf("popV:");
    for(auto &i:popV)
        printf("%d ",i);
    printf("\n");
    if(Q3_IsPopOrder(pushV,popV))
        qDebug()<<"测试3通过";
    else
        qDebug()<<"测试3不通过";
}

bool Q3_IsPopOrder(vector<int> pushV, vector<int> popV)
{
    if(pushV.empty() || popV.empty())
        return false;
    //    size_t size=sizeof(pushV)/sizeof(pushV[0]);
    stack<int> testStack;
    for(int i=0,j=0;i<pushV.size();++i){
        testStack.push(pushV[i]);
        while(j<popV.size() && testStack.top() == popV[j]){
            testStack.pop();
            ++j;
        }
    }
    return testStack.empty();
}
